Сообщений 6 
Оценка 200
[+1/-1]
Оценить 
| Сообщений 6 Оценка 200
[+1/-1]
Оценить
|
| Простейший алгоритм размножения. Анализ алгоритма Живые Пиксели Эволюция История Программа NeoNeuro Живые Пиксели Заключение Список литературы |
В последние десятилетия программирование прочно заняло лидирующее место в развитии мировой экономики. Феноменальные успехи Microsoft, Apple, Google и FaceBook доказывают, что именно алгоритмизация и оптимизация рутинных процессов является главным вектором развития научно-технического прогресса. Программирование сейчас касается уже и простых пользователей – всё больше программ имеют встроенное API, более того – настройка коммуникаторов и даже работа с современной бытовой техникой, по сути, является программированием, доступным каждому.
Поведение человека и вообще любого живого существа можно рассматривать как реализацию внутренней программы.
Если программирование занимает столь важную часть в жизнедеятельности человека, то интересно разобраться, что же лежит в основе программирования? К примеру, каким образом мог появиться такой сложный самонастраиваемый и саморазвивающийся "механизм", как Человек? Теория Дарвина легла в основу "генетического алгоритма", который своей эффективностью доказывает, что природные алгоритмы действительно хороши и способны развиваться самостоятельно до сложнейших оптимизированных конструкций. И всё же генетический алгоритм достаточно сложен, чтобы появится "случайно", в природе он появляется лишь на высших ступенях развития эволюции, поэтому "базовым" его считать нельзя. Базовый алгоритм должен быть максимально простым – и при этом достаточным, чтобы из него могли родиться любые, самые сложные формы жизни. Существует ли такой "базовый" алгоритм в действительности, и каков он, пока неизвестно. Наиболее интересной попыткой разобраться в природных базовых алгоритмах является теория клеточных автоматов, которая рассматривает, насколько сложные фигуры могут появиться на листе бумаги в клетку, если зарисовывать отдельные клетки шаг за шагом, используя на каждом шагу предыдущий рисунок и некое простое правило появления и исчезновения закрашенных, "живых", клеток.
Данная статья высказывает теорию о том, что базовым алгоритмом может быть простая инверсия, при которой "живой" элемент меняет состояние соседей на противоположное. Данного алгоритма достаточно для образования сложнейших фракталов, сохранения наследственности, появления циклов и статических объектов. Алгоритм является математической абстракцией, на базе которой можно изучать различные явления из жизни – от деления клетки ДНК до философских законов, таких как переход количества в качество.
Живые Пиксели — это сложнейший мир, рождённый всего из одного правила.
Живые Пиксели — это «клеточный автомат» - последовательное изменение рисунка, состоящего из активных и пустых клеток, где каждый новый образ создаётся из предыдущего по определённым правилам. В Живых Пикселях правило только одно — активная клетка меняет состояние всех 8 соседних на противоположное. Равносильное правило — если для клетки число активных соседей нечетное, она становится активной, если четное — то пустой. В теории клеточных автоматов правило можно записать как B1357/S1357 – B: born – рождённые, S: suvirval – оставшиеся, цифры означают количество соседей.
Активный пиксель в центре меняет состояние пустых клеток рядом на активное. Сам становится пустым, потому что все пиксели по умолчанию пустые, а активных соседей у центрального пикселя в начальный момент нет:
Если взять квадрат два на два и поместить туда один активный пиксель, то получатся два циклически повторяющихся варианта:
Начальный пиксель делает активными три других, затем три активных пикселя делают активным начальный, а сами становятся пустыми, так как у каждого ДВА «живых» соседа — чётное число, значит, клетка будет пустой.
На следующем рисунке показано, как один активный пиксель эволюционирует в красивый арабский орнамент.
В Живых Пикселях рассматривается в первую очередь двумерная матрица и «расширенное» количество соседей — 8 штук, ход шахматного короля, в теории клеточных автоматов 8 соседних клеток называются «окрестностью Мура». При этом алгоритм актуален и показывает интересные возможности и на одномерной, трёхмерной и многомерной матрице, а также может быть использован для «укороченного» числа соседей — 4 клеток, без учёта диагональных. В Живых Пикселях поле считается ограниченным, при этом неограниченную матрицу можно считать частным случаем ограниченной со «стенками», удалёнными на бесконечное расстояние.
Одно простое правило даёт удивительные и неожиданные открытия:
Удивительно, как из "морской пены" рождается осмысленное изображение:
Алгоритм Живые Пиксели реализован в одноимённой бесплатной программе, которую можно скачать здесь:
Сайт: www.neoneuro.com
Кроме алгоритма Живые Пиксели, в программе также реализован алгоритм «Эволюция», имитирующий развитие биологических видов из нескольких простых правил, а также «Игра Жизнь» математика Конвея.
Разберём различные варианты, которые даёт алгоритм Живых Пикселей – различные сочетания активных и пустых пикселей, одномерную и двумерные ограниченные и неограниченные матрицы.
Все указанные примеры можно найти в программе. Скачать
"Живые Пиксели" - система изменения пикселей, когда каждый активный пиксель меняет состояние соседних пикселей на противоположное: активный становится пустым, а пустой - активным. Простое правило образует очень сложные конструкции.
Один живой пиксель на бесконечном поле имитирует Большой Взрыв Вселенной.На 21-ом ходу картинка представляет собой квадрат, состоящий из восьми квадратов, каждый их которых также состоит из восьми квадратов, каждый из которых состоит из восьми пикселей. Такое подобие называется фракталом, наша Вселенная также имеет структуру фрактала: Галактики вращаются вокруг центра Вселенной, Звезды вращаются вокруг центров Галактик, Планеты вокруг Звезд, Электроны вокруг Ядер атомов.
Изменение числа активных пикселей на каждом шагу образует очень интересный математический ряд:
1 8 8 24 8 64 24 112 8 64 192 24 192 112 416 8 64 64 192 64 512 192 896 24 192 192 576 112 896 416 1728 8
С одной стороны, число пикселей постоянно увеличивается, с другой - их число неизменно возращается к 8! На рисунке такое обращение кажется волшебным: из причудливого зелёного тумана выходит новорожденный – те же 8 пикселей, но на большем расстоянии друг от друга. Типичный "переход количества в качество". Ровно 8 пикселей на экране мы видим в моменты, соответствующие круглым числам с одной единицей в двоичной системе (десятичное число - двоичное представление): 1-1, 2-10, 4-100, 8-1000, 16-10000 и т.д. Тот же ряд, представленный в двоичном виде:
1 1000 1000 11000 1000 1000000 11000 1110000 1000 1000000 11000000 11000 11000000 1110000 110100000 1000 1000000 1000000 11000000 1000000 1000000000 11000000 1110000000 11000 11000000 11000000 1001000000 1110000 1110000000 110100000 11011000000 1000
Большинство чисел имеют вначале единицы, затем нули. Ещё один ряд, составленный из количества единиц в вышеуказанном ряде:
1 1 1 2 1 1 2 3 1 1 2 2 3 3 1 1 1 2 1 1 2 3 2 2 2 2 3 3 3 4 1
Если применить его к клавишам фортепьяно, то получается гармоничная музыка…
Размножение является очень интересной особенностью Больших Пикселей. Знак LP через 16 ходов превращается в 8 таких же знаков. На бесконечном поле любое изображение будет подобным образом размножаться:
Данный эффект ранее был описан профессором математики Эдвардом Фредкиным.
Расчёты показывают, что «период размножения» зависит от размеров начального паттерна и составляет 8 шагов для паттерна, который «входит» в квадрат в 8 пикселей, 16 шагов для паттерна с максимальным размером от 9 до 16 и так далее. «Период размножения» можно рассчитать так: 2x, где x > 2 и максимальная ширина или высота паттерна меньше или равна x.
Рассмотрим простейшие случаи Живых Пикселей.
Одна клетка:
Пустой Пиксель- ничего не происходит.
Активный Пиксель - становится пустым на первом ходу.
Две клетки:
В первом случае наблюдаем маятник - последовательное движение живого Пикселя вправо-влево.
Во втором случае два Живых Пикселя составляют простейшую статическую фигуру.
Три клетки:
Все фигуры исчезают.
Четыре клетки:
Все фигуры возвращаются в начальное состояние. Это простейший случай сохранения наследственности. См. далее ДНК.
Анализ вариантов из двух рядов.
В этом случае элементы либо становятся статическими, либо мигают как сигнальные лампочки.
Фигуры делятся и бегают вправо-влево. Пример можно посмотреть в программе.
Квадраты — квадратные матрицы — поля с одинаковым количеством колонок и рядов. Некоторые квадраты дают уникальные возможности полного обращения рисунка в начальное состояние.
Квадрат 2x2 содержит два "мигающих" варианта, переходящих один в другой, и два статических.
4x4
Встречаются фигуры, обладающие обратимостью. Большинство указанных фигур необратимы, при этом превращаются в обратимые фигуры с периодом 6 - у некоторых период 3, ввиду симметричности.
3x3 - все варианты исчезают
5x5 - пиксель в углу превращается в конструкцию с периодом обращения 4
6x6 – 1 активный пиксель в углу
Обратимость за 14 ходов
8x8 – 1 активный пиксель в углу
Обратимость за 14 ходов
Таблица обратимости чётных квадртатов:
|
Размер |
2x2 |
4x4 |
6x6 |
8x8 |
10x10 |
12x12 |
14x14 |
16x16 |
18x18 |
20x20 |
|
Период |
2/0* |
6/3/нет |
14 |
14 |
62 |
126 |
30/нет |
30/нет |
1022 |
126 |
|
Размер |
22x22 |
24x24 |
26x26 |
28x28 |
30x30 |
32x32 |
34x34 |
36x36 |
38x38 |
40x40 |
|
Период |
4094 |
2046/нет |
1022 |
32766 |
62 |
62 |
8190/Нет |
Нет |
8190 |
2046 |
*дробь означает, что для некоторых паттернов – начальных рисунков – обратимости нет, либо существуют статические неизменные фигуры, с обратимостью 0, либо есть частные случаи обратимости в меньшее количество шагов, что случается для некоторых симметричных фигур.
Здесь мы наблюдаем ещё один математический ряд:
2 6 14 14 62 126 30 30 1022 126 4094 2046 1022 32766 62 62 8190 ? 8190 2046
Все числа ряда являются числами, входящими в множество 2x – 2, где x – чётное число, начиная с 2х.
Чётные квадраты могут быть использованы на практике для шифрования. Найти "обратный" алгоритм, чтобы выяснить предыдущее состояние паттерна «Живых Пикселей» очень сложно, не исключено что практически невыгодно. При этом "прямой прогон" любого изображения в обратимом чётном квадрате даст начальное изображение через большое, заранее известное число итераций. Не буду вдаваться в детали теории шифрования и оставлю вопрос конкретных методик использования для этих целей «Живых Пикселей» открытым.
Разбирая одномерное, то есть линейное поле, можно имитировать копирование ДНК и сохранение наследственной информации. Любая последовательность живых пикселей со временем повторяется и размножается. В данном случае записано число 19 в двоичном виде: 1011.
На четвертом шагу цифра повторяется, на 8-ом - повторяется еще раз, плюс образуется зеркальная фигура слева. На 24-ом ходу мы видим две фигуры из 8-го хода. Цифра 1011 видна в правой половине каждой из них. Таким образом, наблюдаем наследование родительских признаков, подобно тому, как это происходит в ДНК.
Алгоритм, имитирующий развитие биологических видов – от простейших микроорганизмов до огромных динозавров и разумных людей. Данный алгоритм был разработан до «Живых Пикселей» и является самостоятельным клеточным автоматом.
Элемент — набор пикселей, лежащих рядом. Элементы раскрашены в зависимости от количества пикселей в них.
«Эволюцию» можно рассматривать как развитие отдельных живых существ, хотя правильнее рассматривать её как развитие видов. Каждый элемент — есть определённый вид организмов.
Для удобства элементы из одного пикселя показаны зелёным, из двух — тёмно-красным, из трёх — светло-красным, из четырёх — синим. Наиболее распространёнными являются элементы из одного и двух пикселей. На рисунке видно, что элемент из четырёх пикселей всего один. Наиболее крупные элементы живут долго, затем надолго исчезают — как динозавры.
Жизнь вышла из океана. На изображении серые полоски внизу имитируют изрезанное морское дно. Интересно проследить, как зависит размер животных видов от среды обитания — чем больше у вида пространства, тем больше размер наибольших живых существ. При этом мелкие животные встречаются повсюду.
Видна явная связь между размерами вида и местом обитания. В расщелины внизу может "залезть" любой «зверь», при этом в основном там объекты в один или два пикселя.
Прообразом современных клеточных автоматов можно считать треугольник Паскаля, известный с десятого века. Вот что пишет Википедия [5]:
Если очертить треугольник Паскаля, то получится равнобедренный треугольник. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Продолжать треугольник можно бесконечно. Строки треугольника симметричны относительно вертикальной оси. Имеет применение втеории вероятностей и обладает занимательными свойствами.
Если заменить нечётные числа точками, а чётные сделать прозрачными, то получаем треугольник Серпинского:
Рекомендую обзор треугольников Паскаля и Серпинского, опубликованный на Арбузе.
Опять обратимся к Википедии [1]:
"Станислав Улам, работая в Лос-аламосской национальной лаборатории в 1940-е годы, изучал рост кристаллов, используя простую решёточную модель. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель известна как кинематическая. Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота и, в частности, обеспечения необходимого "запаса частей", из которого должен строиться робот. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом возникла первая клеточно-автоматная система. Подобно решётке Улама, клеточный автомат фон Неймана двухмерный, а самовоспроизводящийся робот описан алгоритмически. Результатом явился универсальный конструктор, работающий "внутри" клеточного автомата с окрестностью, включающей непосредственно прилегающие ячейки, и имеющего 29 состояний. Фон Нейман доказал, что для такой модели существует паттерн, который будет бесконечно копировать самого себя."
Алгоритм Живые Пиксели на бесконечном поле бесконечно копирует любой начальное расположение активных пикселей, то есть решает задачу фон Неймана.
Определение клеточного автомата из Википедии:
"Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Включает регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Решетка может быть любой размерности. Для каждой ячейки определено множество ячеек, называемых соседством. К примеру, соседство может быть определено как все ячейки на расстоянии не более 2 от текущей. Для работы клеточного автомата требуется задание начального состояния всех ячеек, и правил перехода ячеек из одного состояния в другое. На каждой итерации, используя правила перехода и состояния соседних ячеек, определяется новое состояние каждой ячейки. Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко всей решётке."
Достаточно обширный анализ клеточных автоматов сделан в программе Cellular Automata Laboratory (http://www.fourmilab.ch/cellab/cellab.zip) В программе реализованы 37 видов автоматов, которые описаны по-английски на странице http://www.fourmilab.ch/cellab/manual/rules.html Примеры к программе не используют алгоритм, повторяющий Живые Пиксели, изучение описаний алгоритмов показывает, что Живые Пиксели являются частным случаем алгоритма Эдварда Фредкина Fredmem. Близким к Живым Пикселям является алгоритм Fractal, который также является частным случаем алгоритма Fredmem. Эдвард Фредкин указывает на то, что его алгоритм является примером «самовоспроизводства», то есть «размножения» - начальная фигура через определённое число итераций превращается в несколько таких же фигур. Такую картину мы наблюдаем в Живых Пикселях на бесконечном поле.
Ещё более полная подборка клеточных автоматов приводится на сайте http://www.mirekw.com/ca/rullex_wlif.html
Алгоритмы «Эволюция», и затем «Живые Пиксели» были разработаны и программно реализованы в 2012м году. На сегодняшний день многие аспекты алгоритмов остаются неизученными. Читатель может принять участие в анализе «Живых Пикселей» и «Эволюции» и поиске интересных конструкций, используя программу NeoNeuro Live Pixels – Живые Пиксели.
Внешний вид:
Программа показывает поле с «пикселями» и описание каждого алгоритма. Простой и удобный редактор позволяет создавать новые конструкции, анализировать их работу и сохранять в файл, который можно выложить в интернет для всеобщего обозрения.
Позволяет выбрать сцену для любого из трёх алгоритмов:
Живые Пиксели
Эволюция
Игра Жизнь
Поле развития клеточных алгоритмов. Щелчком мыши можно сделать ход. "Тип ячейки" в правой панели позволяет менять функциональность клавиш мыши.
Внизу описание конкретного алгоритма.
Шаг - один шаг программы. Равносильно щелчку мыши в режиме "шаг".
Назад - возвращает на один шаг назад.
Очистить - обнуляет поле.
В начало - возвращает поле в начальное положение.
Поехали! - автоматически меняет сцены. Кнопка превращается в "Быстрее".
Стоп - остановка автоматической смены сцен.
Тип ячейки - выбор функциональности щелчка мыши по матрице. Движение мышью с нажатой левой клавишей по матрице позволяет "рисовать" требуемое изображение быстрее.
Внизу правой колонки основные возможности настройки матрицы.
Интерфейс программы реализован на русском, английском и немецком языках, пользователи имеют возможность добавить новые переводы.
Спасибо за то, что ознакомились с миром Живых Пикселей. Надеюсь, он вам понравился. Приглашаю всех желающих продолжить поиск интересных явлений и конструкций в «Живых Пикселях» и «Эволюции» – редактор в программе достаточно удобен для этих целей.
Сайт: www.neoneuro.com
| Сообщений 6 Оценка 200
[+1/-1]
Оценить
|